ラボ7：優先度付きキューとヒープ

これから作るものは？🎯

  • データ構造：　優先度付きキュー（PQ）。
    • これはリストやキューのような抽象データ型ですが、ちょっとした特徴があります。
    • 各アイテムには「優先度」（キー）が割り当てられます。
    • 「pop」操作を行うと、あなたは常に常に最も優先度が高いアイテムを取得します。
  • 操作：
    • 1. push(k)
    • 2. peek()
    • 3. pop()
  • 実装方法：私たちは二分最大ヒープを使います。
  • なぜヒープを使うのか？効率的です！ヒープを使うことで、次のような性能が得られます：
    • push: O(log N)
    • pop: O(log N)
    • peek: O(1)

什么是最大ヒープですか？

2つの簡単なルールを持つ二分木です：

1. 形状の性質

それは完全二分木です。すべてのレベルが埋まっていますが、最後のレベルだけは左から右に順に埋まる場合もあります。隙間はありません。

葉をクリックして削除してください

2. 最大ヒープの性質

親のキーは子のキー以上子のキー以上です。これにより、最大値要素は常に根に位置します。

木の格納方法 💾

木が完全であるため、単純な配列に完璧に格納できます。

インデックス計算（0ベース）

インデックスiにあるノードについて：

  • 親(i - 1) // 2
  • 左の子2 * i + 1
  • 右の子2 * i + 2

アドバイス：これらの公式を暗記しましょう！これらが配列内の「木」を操作する鍵です。